(function () {

	/**
 * Utility class for sampling weighted random points on the surface of a mesh.
 *
 * Building the sampler is a one-time O(n) operation. Once built, any number of
 * random samples may be selected in O(logn) time. Memory usage is O(n).
 *
 * References:
 * - http://www.joesfer.com/?p=84
 * - https://stackoverflow.com/a/4322940/1314762
 */

	const _face = new THREE.Triangle();

	const _color = new THREE.Vector3();

	class MeshSurfaceSampler {

		constructor(mesh) {

			let geometry = mesh.geometry;

			if (!geometry.isBufferGeometry || geometry.attributes.position.itemSize !== 3) {

				throw new Error('THREE.MeshSurfaceSampler: Requires BufferGeometry triangle mesh.');

			}

			if (geometry.index) {

				console.warn('THREE.MeshSurfaceSampler: Converting geometry to non-indexed BufferGeometry.');
				geometry = geometry.toNonIndexed();

			}

			this.geometry = geometry;
			this.randomFunction = Math.random;
			this.positionAttribute = this.geometry.getAttribute('position');
			this.colorAttribute = this.geometry.getAttribute('color');
			this.weightAttribute = null;
			this.distribution = null;

		}

		setWeightAttribute(name) {

			this.weightAttribute = name ? this.geometry.getAttribute(name) : null;
			return this;

		}

		build() {

			const positionAttribute = this.positionAttribute;
			const weightAttribute = this.weightAttribute;
			const faceWeights = new Float32Array(positionAttribute.count / 3); // Accumulate weights for each mesh face.

			for (let i = 0; i < positionAttribute.count; i += 3) {

				let faceWeight = 1;

				if (weightAttribute) {

					faceWeight = weightAttribute.getX(i) + weightAttribute.getX(i + 1) + weightAttribute.getX(i + 2);

				}

				_face.a.fromBufferAttribute(positionAttribute, i);

				_face.b.fromBufferAttribute(positionAttribute, i + 1);

				_face.c.fromBufferAttribute(positionAttribute, i + 2);

				faceWeight *= _face.getArea();
				faceWeights[i / 3] = faceWeight;

			} // Store cumulative total face weights in an array, where weight index
			// corresponds to face index.


			this.distribution = new Float32Array(positionAttribute.count / 3);
			let cumulativeTotal = 0;

			for (let i = 0; i < faceWeights.length; i++) {

				cumulativeTotal += faceWeights[i];
				this.distribution[i] = cumulativeTotal;

			}

			return this;

		}

		setRandomGenerator(randomFunction) {

			this.randomFunction = randomFunction;
			return this;

		}

		sample(targetPosition, targetNormal, targetColor) {

			const cumulativeTotal = this.distribution[this.distribution.length - 1];
			const faceIndex = this.binarySearch(this.randomFunction() * cumulativeTotal);
			return this.sampleFace(faceIndex, targetPosition, targetNormal, targetColor);

		}

		binarySearch(x) {

			const dist = this.distribution;
			let start = 0;
			let end = dist.length - 1;
			let index = - 1;

			while (start <= end) {

				const mid = Math.ceil((start + end) / 2);

				if (mid === 0 || dist[mid - 1] <= x && dist[mid] > x) {

					index = mid;
					break;

				} else if (x < dist[mid]) {

					end = mid - 1;

				} else {

					start = mid + 1;

				}

			}

			return index;

		}

		sampleFace(faceIndex, targetPosition, targetNormal, targetColor) {

			let u = this.randomFunction();
			let v = this.randomFunction();

			if (u + v > 1) {

				u = 1 - u;
				v = 1 - v;

			}

			_face.a.fromBufferAttribute(this.positionAttribute, faceIndex * 3);

			_face.b.fromBufferAttribute(this.positionAttribute, faceIndex * 3 + 1);

			_face.c.fromBufferAttribute(this.positionAttribute, faceIndex * 3 + 2);

			targetPosition.set(0, 0, 0).addScaledVector(_face.a, u).addScaledVector(_face.b, v).addScaledVector(_face.c, 1 - (u + v));

			if (targetNormal !== undefined) {

				_face.getNormal(targetNormal);

			}

			if (targetColor !== undefined && this.colorAttribute !== undefined) {

				_face.a.fromBufferAttribute(this.colorAttribute, faceIndex * 3);

				_face.b.fromBufferAttribute(this.colorAttribute, faceIndex * 3 + 1);

				_face.c.fromBufferAttribute(this.colorAttribute, faceIndex * 3 + 2);

				_color.set(0, 0, 0).addScaledVector(_face.a, u).addScaledVector(_face.b, v).addScaledVector(_face.c, 1 - (u + v));

				targetColor.r = _color.x;
				targetColor.g = _color.y;
				targetColor.b = _color.z;

			}

			return this;

		}

	}

	THREE.MeshSurfaceSampler = MeshSurfaceSampler;

})();
